PittsburghV1, France, Analysis, bibRecord, 000381

Stability of the bipartite matching model

Identifieur interne : 000381 ( France/Analysis ); précédent : 000380; suivant : 000382

Stability of the bipartite matching model

Auteurs : Ana Busic [France] ; Varun Gupta [États-Unis] ; Jean Mairesse [France]

Source :

Advances in Applied Probability [ 0001-8678 ] ; 2013-06.

RBID : Hal:hal-00835437

English descriptors

mix :
- Markovian queueing theory, bipartite matching, stability.

Abstract

We consider the bipartite matching model of customers and servers introduced by Caldentey, Kaplan and Weiss (2009). Customers and servers play symmetrical roles. There are finite sets C and S of customer and server classes, respectively. Time is discrete and at each time step one customer and one server arrive in the system according to a joint probability measure μ on C× S, independently of the past. Also, at each time step, pairs of matched customers and servers, if they exist, depart from the system. Authorized em matchings are given by a fixed bipartite graph (C, S, E⊂ C × S). A matching policy is chosen, which decides how to match when there are several possibilities. Customers/servers that cannot be matched are stored in a buffer. The evolution of the model can be described by a discrete-time Markov chain. We study its stability under various admissible matching policies, including ML (match the longest), MS (match the shortest), FIFO (match the oldest), RANDOM (match uniformly), and PRIORITY. There exist natural necessary conditions for stability (independent of the matching policy) defining the maximal possible stability region. For some bipartite graphs, we prove that the stability region is indeed maximal for any admissible matching policy. For the ML policy, we prove that the stability region is maximal for any bipartite graph. For the MS and PRIORITY policies, we exhibit a bipartite graph with a non-maximal stability region.

Url:

https://hal.inria.fr/hal-00835437

DOI: 10.1239/aap/1370870122

Affiliations:

France, États-Unis

Links toward previous steps (curation, corpus...)

to stream Hal, to step Corpus: 000565
to stream Hal, to step Curation: 000565
to stream Hal, to step Checkpoint: 000291
to stream Main, to step Merge: 005D78
to stream Main, to step Curation: 005A40
to stream Main, to step Exploration: 005A40
to stream France, to step Extraction: 000381

Links to Exploration step

Hal:hal-00835437

Le document en format XML

<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Stability of the bipartite matching model</title>
<author><name sortKey="Busic, Ana" sort="Busic, Ana" uniqKey="Busic A" first="Ana" last="Busic">Ana Busic</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-160294" status="VALID">          <orgName>Laboratory of Information, Network and Communication Sciences</orgName>
          <orgName type="acronym">LINCS</orgName>
          <desc>            <address>              <addrLine>23 avenue d'Italie 75013 Paris</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.lincs.fr/</ref>
          </desc>
          <listRelation>            <relation active="#struct-93591" type="direct"></relation>
            <relation active="#struct-300009" type="direct"></relation>
            <relation active="#struct-302102" type="direct"></relation>
          </listRelation>
        <tutelles><tutelle active="#struct-93591" type="direct"><org type="institution" xml:id="struct-93591" status="VALID">          <orgName>Université Pierre et Marie Curie - Paris 6</orgName>
          <orgName type="acronym">UPMC</orgName>
          <desc>            <address>              <addrLine>4 place Jussieu - 75005 Paris</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.upmc.fr/</ref>
          </desc>
        </org>
</tutelle>
<tutelle active="#struct-300009" type="direct"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
<orgName type="acronym">Inria</orgName>
<desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/en/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-302102" type="direct"><org type="institution" xml:id="struct-302102" status="VALID">          <orgName>Institut Mines-Télécom [Paris]</orgName>
          <desc>            <address>              <addrLine>37-39 Rue Dareau, 75014 Paris</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.mines-telecom.fr/</ref>
          </desc>
        </org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
</affiliation>
</author>
<author><name sortKey="Gupta, Varun" sort="Gupta, Varun" uniqKey="Gupta V" first="Varun" last="Gupta">Varun Gupta</name>
<affiliation wicri:level="1"><hal:affiliation type="institution" xml:id="struct-67135" status="VALID">          <orgName>Carnegie Mellon University [Pittsburgh]</orgName>
          <orgName type="acronym">CMU</orgName>
          <desc>            <address>              <addrLine>5000 Forbes Ave,  Pittsburgh, PA 15213</addrLine>
              <country key="US"></country>
            </address>
            <ref type="url">http://www.cmu.edu/</ref>
          </desc>
        </hal:affiliation>
<country>États-Unis</country>
</affiliation>
</author>
<author><name sortKey="Mairesse, Jean" sort="Mairesse, Jean" uniqKey="Mairesse J" first="Jean" last="Mairesse">Jean Mairesse</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-1033" status="OLD">          <orgName>Laboratoire d'informatique Algorithmique : Fondements et Applications</orgName>
          <orgName type="acronym">LIAFA</orgName>
          <date type="end">2015-12-31</date>
          <desc>            <address>              <addrLine>Université Paris Diderot, Bât. Sophie Germain, case postale 7014, 75205 Paris cedex 13</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.liafa.jussieu.fr/</ref>
          </desc>
          <listRelation>            <relation active="#struct-300301" type="direct"></relation>
            <relation name="UMR7089" active="#struct-441569" type="direct"></relation>
          </listRelation>
        <tutelles><tutelle active="#struct-300301" type="direct"><org type="institution" xml:id="struct-300301" status="VALID">          <orgName>Université Paris Diderot - Paris 7</orgName>
          <orgName type="acronym">UPD7</orgName>
          <desc>            <address>              <addrLine>5 rue Thomas-Mann - 75205 Paris cedex 13</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.univ-paris-diderot.fr</ref>
          </desc>
        </org>
</tutelle>
<tutelle name="UMR7089" active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID">          <idno type="IdRef">02636817X</idno>
          <idno type="ISNI">0000000122597504</idno>
          <orgName>Centre National de la Recherche Scientifique</orgName>
          <orgName type="acronym">CNRS</orgName>
          <date type="start">1939-10-19</date>
          <desc>            <address>              <country key="FR"></country>
            </address>
            <ref type="url">http://www.cnrs.fr/</ref>
          </desc>
        </org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">HAL</idno>
<idno type="RBID">Hal:hal-00835437</idno>
<idno type="halId">hal-00835437</idno>
<idno type="halUri">https://hal.inria.fr/hal-00835437</idno>
<idno type="url">https://hal.inria.fr/hal-00835437</idno>
<idno type="doi">10.1239/aap/1370870122</idno>
<date when="2013-06">2013-06</date>
<idno type="wicri:Area/Hal/Corpus">000565</idno>
<idno type="wicri:Area/Hal/Curation">000565</idno>
<idno type="wicri:Area/Hal/Checkpoint">000291</idno>
<idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">000291</idno>
<idno type="wicri:doubleKey">0001-8678:2013:Busic A:stability:of:the</idno>
<idno type="wicri:Area/Main/Merge">005D78</idno>
<idno type="wicri:Area/Main/Curation">005A40</idno>
<idno type="wicri:Area/Main/Exploration">005A40</idno>
<idno type="wicri:Area/France/Extraction">000381</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en">Stability of the bipartite matching model</title>
<author><name sortKey="Busic, Ana" sort="Busic, Ana" uniqKey="Busic A" first="Ana" last="Busic">Ana Busic</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-160294" status="VALID">          <orgName>Laboratory of Information, Network and Communication Sciences</orgName>
          <orgName type="acronym">LINCS</orgName>
          <desc>            <address>              <addrLine>23 avenue d'Italie 75013 Paris</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.lincs.fr/</ref>
          </desc>
          <listRelation>            <relation active="#struct-93591" type="direct"></relation>
            <relation active="#struct-300009" type="direct"></relation>
            <relation active="#struct-302102" type="direct"></relation>
          </listRelation>
        <tutelles><tutelle active="#struct-93591" type="direct"><org type="institution" xml:id="struct-93591" status="VALID">          <orgName>Université Pierre et Marie Curie - Paris 6</orgName>
          <orgName type="acronym">UPMC</orgName>
          <desc>            <address>              <addrLine>4 place Jussieu - 75005 Paris</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.upmc.fr/</ref>
          </desc>
        </org>
</tutelle>
<tutelle active="#struct-300009" type="direct"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
<orgName type="acronym">Inria</orgName>
<desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/en/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-302102" type="direct"><org type="institution" xml:id="struct-302102" status="VALID">          <orgName>Institut Mines-Télécom [Paris]</orgName>
          <desc>            <address>              <addrLine>37-39 Rue Dareau, 75014 Paris</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.mines-telecom.fr/</ref>
          </desc>
        </org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
</affiliation>
</author>
<author><name sortKey="Gupta, Varun" sort="Gupta, Varun" uniqKey="Gupta V" first="Varun" last="Gupta">Varun Gupta</name>
<affiliation wicri:level="1"><hal:affiliation type="institution" xml:id="struct-67135" status="VALID">          <orgName>Carnegie Mellon University [Pittsburgh]</orgName>
          <orgName type="acronym">CMU</orgName>
          <desc>            <address>              <addrLine>5000 Forbes Ave,  Pittsburgh, PA 15213</addrLine>
              <country key="US"></country>
            </address>
            <ref type="url">http://www.cmu.edu/</ref>
          </desc>
        </hal:affiliation>
<country>États-Unis</country>
</affiliation>
</author>
<author><name sortKey="Mairesse, Jean" sort="Mairesse, Jean" uniqKey="Mairesse J" first="Jean" last="Mairesse">Jean Mairesse</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-1033" status="OLD">          <orgName>Laboratoire d'informatique Algorithmique : Fondements et Applications</orgName>
          <orgName type="acronym">LIAFA</orgName>
          <date type="end">2015-12-31</date>
          <desc>            <address>              <addrLine>Université Paris Diderot, Bât. Sophie Germain, case postale 7014, 75205 Paris cedex 13</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.liafa.jussieu.fr/</ref>
          </desc>
          <listRelation>            <relation active="#struct-300301" type="direct"></relation>
            <relation name="UMR7089" active="#struct-441569" type="direct"></relation>
          </listRelation>
        <tutelles><tutelle active="#struct-300301" type="direct"><org type="institution" xml:id="struct-300301" status="VALID">          <orgName>Université Paris Diderot - Paris 7</orgName>
          <orgName type="acronym">UPD7</orgName>
          <desc>            <address>              <addrLine>5 rue Thomas-Mann - 75205 Paris cedex 13</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.univ-paris-diderot.fr</ref>
          </desc>
        </org>
</tutelle>
<tutelle name="UMR7089" active="#struct-441569" type="direct"><org type="institution" xml:id="struct-441569" status="VALID">          <idno type="IdRef">02636817X</idno>
          <idno type="ISNI">0000000122597504</idno>
          <orgName>Centre National de la Recherche Scientifique</orgName>
          <orgName type="acronym">CNRS</orgName>
          <date type="start">1939-10-19</date>
          <desc>            <address>              <country key="FR"></country>
            </address>
            <ref type="url">http://www.cnrs.fr/</ref>
          </desc>
        </org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
</affiliation>
</author>
</analytic>
<idno type="DOI">10.1239/aap/1370870122</idno>
<series><title level="j">Advances in Applied Probability</title>
<idno type="ISSN">0001-8678</idno>
<imprint><date type="datePub">2013-06</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass><keywords scheme="mix" xml:lang="en"><term>Markovian queueing theory</term>
<term>bipartite matching</term>
<term>stability</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">We consider the bipartite matching model of customers and servers introduced by Caldentey, Kaplan and Weiss (2009). Customers and servers play symmetrical roles. There are finite sets C and S of customer and server classes, respectively. Time is discrete and at each time step one customer and one server arrive in the system according to a joint probability measure μ on C× S, independently of the past. Also, at each time step, pairs of matched customers and servers, if they exist, depart from the system. Authorized em matchings are given by a fixed bipartite graph (C, S, E⊂ C × S). A matching policy is chosen, which decides how to match when there are several possibilities. Customers/servers that cannot be matched are stored in a buffer. The evolution of the model can be described by a discrete-time Markov chain. We study its stability under various admissible matching policies, including ML (match the longest), MS (match the shortest), FIFO (match the oldest), RANDOM (match uniformly), and PRIORITY. There exist natural necessary conditions for stability (independent of the matching policy) defining the maximal possible stability region. For some bipartite graphs, we prove that the stability region is indeed maximal for any admissible matching policy. For the ML policy, we prove that the stability region is maximal for any bipartite graph. For the MS and PRIORITY policies, we exhibit a bipartite graph with a non-maximal stability region.</div>
</front>
</TEI>
<affiliations><list><country><li>France</li>
<li>États-Unis</li>
</country>
</list>
<tree><country name="France"><noRegion><name sortKey="Busic, Ana" sort="Busic, Ana" uniqKey="Busic A" first="Ana" last="Busic">Ana Busic</name>
</noRegion>
<name sortKey="Mairesse, Jean" sort="Mairesse, Jean" uniqKey="Mairesse J" first="Jean" last="Mairesse">Jean Mairesse</name>
</country>
<country name="États-Unis"><noRegion><name sortKey="Gupta, Varun" sort="Gupta, Varun" uniqKey="Gupta V" first="Varun" last="Gupta">Varun Gupta</name>
</noRegion>
</country>
</tree>
</affiliations>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Amérique/explor/PittsburghV1/Data/France/Analysis

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000381 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/France/Analysis/biblio.hfd -nk 000381 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Amérique
   |area=    PittsburghV1
   |flux=    France
   |étape=   Analysis
   |type=    RBID
   |clé=     Hal:hal-00835437
   |texte=   Stability of the bipartite matching model
}}

This area was generated with Dilib version V0.6.38.
Data generation: Fri Jun 18 17:37:45 2021. Site generation: Fri Jun 18 18:15:47 2021

	Serveur d'exploration sur Pittsburgh
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.

Serveur d'exploration sur Pittsburgh

Stability of the bipartite matching model

Stability of the bipartite matching model

Source :

English descriptors

Abstract

Links toward previous steps (curation, corpus...)

Links to Exploration step

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri